package com.leetcode.string;

import com.leetcode.math.ListNode;

import java.util.ArrayList;
import java.util.List;

public class FullJustify {
    public static void main(String[] args) {
        String[] words = {"This", "is", "an", "example", "of", "text", "justification."};
        int maxWidth = 16;
        FullJustify fullJustify = new FullJustify();
        System.out.println(fullJustify.fullJustify(words, maxWidth));
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> resList = new ArrayList<>();
        int n = words.length;
        int right = 0; // 单词数组的索引
        while(true) {
            int left = right; // 当前行的第一个单词在数组中的位置
            int sumLen = 0; // 当前行字符的长度
            while(right < n
                    && words[right].length() + right - left + sumLen <= maxWidth) {
                sumLen += words[right++].length();
            }
            // 1.最后一行
            if (right == n) {
                StringBuilder sb = join(words, left, n, " ");
                sb.append(blank(maxWidth - sb.length()));
                resList.add(sb.toString());
                return resList;
            }
            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;
            // 不是最后一行，只有一个单词
            if (numWords == 1) {
                StringBuilder sb = join(words, left, right, " ");
                sb.append(blank(numSpaces));
                resList.add(sb.toString());
                continue;
            }
            // 不是最后一行， 也不只有一个单词
            int averageSpaces = numSpaces / (numWords - 1);
            int extraSpaces = numSpaces % (numWords - 1);
            StringBuilder sb = new StringBuilder();
            sb.append(join(words, left, left + extraSpaces + 1, blank(averageSpaces + 1)));
            sb.append(blank(averageSpaces));
            sb.append(join(words, left + extraSpaces + 1, right, blank(averageSpaces)));
            resList.add(sb.toString());
        }

//        return resList;
    }

    /**
     * 返回由num个空格组成的字符串
     *
     * @param num
     * @return
     */
    private String blank(int num) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < num; i++) {
            stringBuilder.append(" ");
        }
        return stringBuilder.toString();
    }

    /**
     * [left, right) 以sep分割拼接
     *
     * @param words
     * @param left
     * @param right
     * @param sep
     * @return
     */
    private StringBuilder join(String[] words, int left, int right, String sep) {
        StringBuilder stringBuilder = new StringBuilder(words[left]);
        for (int i = left + 1; i < right; i++) {
            stringBuilder.append(sep);
            stringBuilder.append(words[i]);
        }
        return stringBuilder;
    }
}
